import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 967. 连续差相同的数字
 * https://leetcode-cn.com/problems/numbers-with-same-consecutive-differences/
 */
public class Solutions_967 {
    public static void main(String[] args) {
//        int N = 3, K = 7;  // output: {181, 292, 707, 818, 929}
        // 解释：注意，070 不是一个有效的数字，因为它有前导零。

//        int N = 2, K = 1;
        // output: {10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98}

        int N = 2, K = 0;
        // output: {11, 22, 33, 44, 55, 66, 77, 88, 99}

        int[] result = numsSameConsecDiff(N, K);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解题思路：递归法
     * 确定好第 1 位数字后，剩余的 n - 1 位数字，都进行递归来计算完成
     */
    public static int[] numsSameConsecDiff(int n, int k) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i <= 9; i++) {
            // 第 1 位可以为 [0, 9]
            // 当 k == 1 时，第 1 位是可以为 0，但是 k 大于 1 时，第 1 位必须大于 0
            dfs(n, k, 0, list, i);
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    /**
     * 递归计算后 n - 1 位上的数字
     * @param n 位数
     * @param k 差的绝对值
     * @param bit 当前位的索引
     * @param list 结果集
     * @param num 当前构造的数字
     */
    public static void dfs(int n, int k, int bit, List<Integer> list, int num) {
        if (bit > 0 && num < 10) {
            // 不能有前导零
            return;
        }
        if (bit == n - 1) {
            // N 位数字已经计算完成
            list.add(num);
            return;
        }
        int last = num % 10;
        if (last + k <= 9) {
            // 通过 last + k 可以构造出下一位，那么继续构造
            dfs(n, k, bit + 1, list, num * 10 + last + k);
        }
        if (k != 0) {
            // k 为 0 时，只进行一次构造，否则会重复
            // 减 k
            if (last - k >= 0) {
                // 通过 last - k 可以构造出下一位，那么继续构造
                dfs(n, k, bit + 1, list, num * 10 + last - k);
            }
        }
    }
}
